﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GameLibrary.AI.Knapsack
{
    /// <summary>
    /// For 0-1 KP
    /// </summary>
    public static class Greedy
    {
        public static void GetResult(
            int n,
            int c,
            int[] p,
            int[] w,
            out int zg,
            out int[] x
            )
        {
            int[] pj;
            int[] wj;
            List<KeyValuePair<int,int>> mapList;
            KnapsackHelper.SortItem(p, w, out pj, out wj, out mapList);
            int _c = c;
            zg = 0;
            int[] xj = new int[n];
            int jstar = 1;
            for (int j = 0; j < n; j++)
            {
                if (wj[j] > _c)
                    xj[j] = 0;
                else
                {
                    xj[j] = 1;
                    _c = _c - wj[j];
                    zg = zg + pj[j];
                }
                if (pj[j] > pj[jstar])
                    jstar = j;
            }
            if (pj[jstar] > zg)
            {
                zg = pj[jstar];
                for (int j = 0; j < n; j++)
                    xj[j] = 0;
                xj[jstar] = 1;
            }
            KnapsackHelper.GetOriginalSequance(mapList, xj, out x);
        }
    }
}
